\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
\usepackage[cp1251]{inputenc}
\usepackage[russian,english]{babel}
\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\newtheorem {teo} {Theorem}
\usepackage[]{color}%,dvips
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\lexp}{lexp}
\def\U{_\infty^{\phantom{i}a}T}
\usepackage{times}
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\usepackage{wrapfig,floatflt}%,nccfloats
\definecolor{emp}{rgb}{0.2, 0.4, 0.4}
\definecolor{tr}{rgb}{0,0.5,0}
\definecolor{gr}{rgb}{0, 0, 1}
\definecolor{orng}{rgb}{1, 0.5, 0}
\definecolor{rd} {rgb} {1,0,0}
\author[M. Rubinchik, Y. Gamzova, A. Shur]{Mikhail Rubinchik, Yulia Gamzova, Arseny Shur}
\title[Two problems about recovering of damaged
strings.]{Two problems about recovering of damaged
strings.}
\institute[]{Ural Federal University}
\begin{document}
\date{ }
\maketitle

\section{Definition}

\begin{frame}
\centerline{\includegraphics[width=0.5\linewidth]{hamming.pdf}}

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

\end{frame}

\begin{frame}
\centerline{\includegraphics[width=0.5\linewidth]{cycle.png}}

A circular string. No first, no last symbols!
\end{frame}


\section{Problems}

\begin{frame}
\frametitle{Pattern matching}
In the pattern matching problem, an instance is a pair of strings (text, pattern) and it is asked to found all substrings of the text equal to the  pattern. Many linear-time algorithms are known.

For damaged strings, "equal" is replaced by "compatible". The main results are the following:
	\begin{itemize}
	\uncover<2->{
		\item In 1974 M.Fisher and M.Patterson solved pattern matching problem for damaged string in time \alert{$O(|\Sigma||Text|\log|Text|)$}.\\
	}	
	\uncover<3->{
		And for the case of a constant $\Sigma$ they proved that \alert{$O(|Text|\log|Text|)$} is the lower time bound even for partial strings.\\
	}
	\uncover<4->{
		\item In 1992, 1994 S.Muthukrishnan, K.Palem, and H.Ramesh solved the problem for partial string in time \alert{$O(\log|\Sigma||Text|\log|Text|)$}\\
	}	
	\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Problem description}
Suppose we have two damaged strings: a long "text" and a shorter "pattern". Our aim is to recover both strings, replacing all damaged symbols by compatible symbols from $\Sigma$. Among all possible ways of recovery, we want to find the optimal one according to some criterion. 
\end{frame}

\begin{frame}
\frametitle{Problem description}
We consider two criteria, obtaining two optimization problems. \begin{enumerate}
\item Problem \textcolor{blue}{Maximum matches}: Recover the text and the pattern in a way that maximizes the number of matches of the pattern in the text.
\item Problem \textcolor{blue}{Minimum distance}: Recover the text and the pattern in a way that minimizes the total Hamming distance between the text and the pattern. (This distance is calculated as the sum of Hamming distances between the pattern and all substrings of the text having the same length.)
\end{enumerate}

\end{frame}

\section{Main results}
\begin{frame}
\frametitle{Maximum matches}
From now on, let \textbf{n} be the length of the text and \textbf{m} be the length of the pattern.
\begin{block}{Only pattern is damaged}
Solved by algorithm of Fisher and Patterson and building suffix array in time $O(|\Sigma|n\log n)$.
\end{block}
\begin{block}{Only text is damaged}
Solved by dynamic programming with prefix-function in time $O(nm)$.
\end{block}
\begin{block}{General case}
Proved to be NP-hard even if $|\Sigma|=2$ by reduction from maximum clique problem. \end{block}
\end{frame}

\begin{frame}
\frametitle{Minimum distance}
\begin{block}{Only text or only pattern is damaged}
Solved using binary trees in time $O(m\log n + n)$ and $O(n \log m)$ respectively.
\end{block}
\begin{block}{Binary alphabet}
Reduced to maximal flow and solved, for example, by algorithm of Ford-Falkerson in time $O(nm^2)$.
\end{block}
\end{frame}
\begin{frame}
\frametitle{Minimum distance}
\begin{block}{Partial strings [$\Delta=\{\diamond\}$, $\diamond$ compatible to all symbols]}
For circular strings, solved by greedy algorithm in time $O(n{+}m{+}|\Sigma|)$. For ordinary strings, reduced to the multicut problem. Thus, this version is in APX (the class of optimization problems that can be approximated with some constant factor in polynomial time) ; we suggest (but have not proved yet) that this version	 is NP-hard.
\end{block}
\begin{block}{General case}
The problem is proved to be APX-hard and NP-hard even for circular strings by reduction from max-SAT.
\end{block}
\end{frame}



\section{Conclusion}
\begin{frame}
\center{\Huge{Thank you for your attention!}}

\end{frame}
\begin{frame}
\frametitle{Conclusion}

\begin{itemize}

\item Maximum matches
	\begin{itemize}
		\item solved in polynomial time for undamaged text or pattern \\
		\item proved to be NP-hard in general case even for binary alphabet\\
	\end{itemize}
\item Minimum distance \\
	\begin{itemize}
	   \item solved in polynomial time for \\
		\begin{itemize}
			\item undamaged text or pattern\\
			\item binary alphabet\\
			\item partial circular strings\\
		\end{itemize}
		\item proved to be APX-hard and NP-hard in general case even for circular strings
		\item the complexity for partial strings is unclear, but it is know, that problem is in APX\\
	\end{itemize}
\end{itemize}
\end{frame}


\end{document} 